package Review;

import org.omg.CORBA.PUBLIC_MEMBER;
import sun.reflect.generics.tree.Tree;

import javax.xml.bind.annotation.XmlType;
import java.util.*;
import java.util.stream.Stream;

public class TextBinaryTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode root;//定义二叉树的根节点
    //非正规创建一颗二叉树
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.right = H;
        C.left = F;
        C.right = G;
        this.root = A;
        return root;
    }
    //前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    //后序遍历
    public void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
    //前序遍历有返回值
    //此时这个list需要放在外边，否则每次递归都会产生一个新的list
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return list;
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }
    //二叉树的中序遍历有返回值
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        List<Integer> leftTree = inorderTraversal(root.left);
        list.addAll(leftTree);
        list.add(root.val);
        List<Integer> rightTree = inorderTraversal(root.right);
        list.addAll(rightTree);
        return list;
    }
    //二叉树的后序遍历有返回值
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        List<Integer> leftTree = postorderTraversal(root.left);
        list.addAll(leftTree);
        List<Integer> rightTree = postorderTraversal(root.right);
        list.addAll(rightTree);
        list.add(root.val);
        return list;
    }
    //获取二叉树中的节点个数
    //子问题：左树的节点 + 右树的节点 + 1
    //时间复杂度：O(N)  空间复杂度：O(logN)，如果是单分支的树，空间复杂度就是
    //O（N）
    public int size(TreeNode root) {
        if (root == null) return 0;
        return size(root.left) + size(root.right) + 1;
    }
    //遍历思路
    public int count = 0;
    public int size1(TreeNode root) {
        if (root == null) return 0;
        //只要根不为空就++，然后遍历左树和右树
        count++;
        size1(root.left);
        size1(root.right);
        return count;
    }
    //获取叶子节点的个数   子问题思路
    public int getLeafNodeCount(TreeNode root) {
        if (root == null) return 0;//注意：当root为空的时候是没有叶子节点的
        if (root.left == null && root.right == null)
            return 1;
        return getLeafNodeCount(root.left) +
                getLeafNodeCount(root.right);
    }
    //遍历思路
    public int leafCount;
    public void leafNodeCount(TreeNode root) {
        if (root == null) return;
        if (root.left == null && root.right == null)
            leafCount++;
        leafNodeCount(root.left);
        leafNodeCount(root.right);
    }
    //获取第k层的节点个数
    //第k层的节点个数就相当于第k-1层的孩子的节点个数
    public int getLevelNodeCount(TreeNode root, int k) {
        if (root == null) return 0;
        if (k == 1) return 1;
        int left = getLevelNodeCount(root.left, k-1);
        int right = getLevelNodeCount(root.right, k-1);
        return left + right;
    }
    //获取二叉树的高度
    //时间复杂度：O（n）（会遍历到每一个节点）
    public int getHeight(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight,rightHeight) + 1;
    }
    //二叉树的层序遍历
    public void levelOrder1(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
    //二叉树层序遍历有返回值
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> ret = new ArrayList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();
                ret.add(cur.val);
                size--;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(ret);
        }
        return list;
    }
    //判断二叉树中是否存在key值
    /*先看根是否是key，如果不是就去左子树找，在没有就去右子树找*/
    public TreeNode find(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val == key) return root;
        TreeNode left = find(root.left,key);
        if (left != null) return left;
        TreeNode right = find(root.right,key);
        if (right != null) return right;
        return null;
    }
    //相同的树
    //一个空一个不为空，不是    两个都空，是
    //两个都不为空，不一定（需要判断值是否相等）
    /*时间复杂度：O(min(m, n))   空间复杂度：O(min(m, n))*/
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q != null ||
                p != null && q == null) return false;
        if (p == null && q == null) return true;
        //都不为空的情况
        if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    //另一棵树的子树
    /*先判断是否是相同的树，如果是相同的树此时也算是子树
    * 如果不相同，判断是不是root的左子树，是不是root的右子树*/
    /*时间复杂度：O(S * T)   空间复杂度：O(两颗树最大高度的最大值)*/
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null || subRoot == null) {
            return false;
        }
        if (isSameTree(root,subRoot)) return true;
        if (isSubtree(root.left, subRoot)) return true;
        if (isSubtree(root.right, subRoot)) return true;
        return false;
    }
    //反转一颗二叉树
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    //判断一颗树是否为平横二叉树
    //左右高度差不能超过1，就是平衡二叉树
    /*时间复杂度：O(N*2)（每一个节点都要求高度）*/
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.abs(leftHeight-rightHeight) < 2 &&
                isBalanced(root.left) && isBalanced(root.right);
    }
    //在O（n）时间复杂度内判断一棵树是否是平衡二叉树
    //在求二叉树左树和右树的高度的过程中就判断是否满足平衡二叉树
    public int getHeight2(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getHeight(root.left);
        if (leftHeight < 0) return -1;
        int rightHeight = getHeight(root.right);
        if (rightHeight < 0) return -1;
        if (Math.abs(leftHeight-rightHeight) <= 1) {
            return Math.max(leftHeight,rightHeight) + 1;
        }else {
            return -1;
        }
    }
    //判断整棵树是不是对称的，需要判断这棵树的左子树和这棵树的右子树是不是
    //对称的
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isChildSymmetric(root.left, root.right);
    }
    public boolean isChildSymmetric(TreeNode rootL,TreeNode rootR) {
        if (rootL == null && rootR != null || rootL != null && rootR == null)
            return false;
        if (rootL == null && rootR == null) return true;
        //左子树和右子树都不为空
        if (rootL.val != rootR.val) return false;
        return isChildSymmetric(rootL.left, rootR.right) &&
                isChildSymmetric(rootL.right,rootR.left);
    }
    //二叉树的层序遍历
    /*层序遍历就是从上到下，从左到右，是有顺序的，此时需要用合适的数据结构：队列*/
    public void levelOrder(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            //一定是先offer左边，然后是右边，才能保证是层序遍历
            if (cur.left != null) queue.offer(root.left);
            if (cur.right != null) queue.offer(root.right);
        }
    }
    //二叉树的层序遍历 有返回值
    /*此时需要确定哪一层都有哪些节点*/
    public List<List<Integer>> levelOrder3(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> ret = new ArrayList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();
                size--;
                ret.add(cur.val);
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
            list.add(ret);
        }
        return list;
    }
    //二叉树的构建及遍历：读入一颗先序遍历的字符串，创建一颗二叉树
    //然后按中序遍历输出二叉树的节点
    //虽然只是一个前序遍历的字符串，但是也是可以创建出一颗二叉树的（有顺序的前序遍历）
    /*此处的字符串下标是不会越界的，因为给的前序遍历本来就是一个合法的字符串，如果多给了
    * 或者是少给了，此时在创建右树的时候就会发生越界，因为字符串已经遍历完了，但是可能树
    * 还没有建完，所以还会递归，但是现在是合法的字符串，此时递归的时候有回退的次数*/
    public static void main(String[] args) {
        //在main方法中将i置零也是可以的，
        Scanner scan = new Scanner(System.in);
        //将字符串整行都读进来
        String str = scan.nextLine();
        TreeNode root = createTree(str);
        inorder(root);
    }
    public static int i = 0;
    public static TreeNode createTree(String str) {
        TreeNode root = null;
        char ch = str.charAt(i);
        if (ch != '#') {
            root = new TreeNode(ch);
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
    }
    public static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.println(root.val + " ");
        inorder(root.right);
    }
    //二叉树的最近公共祖先
    /*1.在根的两边 2.要么都在根的左边或者右边（其中一个就是公共祖先）*/
    public TreeNode lowestCommonAncestor(
            TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        /*这个地方是找到就返回了，如：在左边先找到了一个节点，此时p和q都在
        * root的左边，但是找到p就结束了，不会再去找另一个节点了，所以返回的
        * 节点就是上边的节点，就是最近的公共祖先*/
        else if (left != null) return left;
        else if (right != null) return right;
        else return null;
    }
    //如果每个节点有了父亲节点的地址，此时就变成了求相交节点
    //但是二叉树没有父亲节点，所以用一个数据结构：栈
    /*把找p和q的路径入到两个栈中，然后元素多的先出差值个元素，之后再一起出
    * 如果元素相等此时这个元素就是最近公共祖先*/

    //找到从根节点到指定节点node路径上所有的节点，然后入栈
    public boolean getPath(TreeNode root,
                           TreeNode node, Deque<TreeNode> stack) {
        if (root == null || node == null) return false;
        stack.push(root);
        if (root == node) return true;
        boolean ret1 = getPath(root.left,node,stack);
        boolean ret2 = getPath(root.right,node,stack);
        if (ret1) return true;
        if (ret2) return true;
        //左边和右边都没找到这个node，此时就回退，让这个元素出栈
        stack.pop();
        return false;//说明这条路径走不通，走到头了，也没找到这个节点
    }
    public TreeNode lowestCommonAncestor2(TreeNode root,
                                          TreeNode p, TreeNode q) {
        //1.两个栈中先存储好数据
        Deque<TreeNode> stack1 = new LinkedList<>();
        getPath(root,p,stack1);
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root,q,stack2);
        //2.判断栈的大小，出差值个元素
        int size1 = stack1.size();
        int size2 = stack2.size();
        //让size1是最大的
        int ret = Math.abs(size1 - size2);
        while (ret != 0) {
            if (size1 > size2) {
                stack1.pop();
            }else {
                stack2.pop();
            }
            ret--;
        }
        //栈中元素个数相等，此时一块出元素
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if (stack1.peek() != stack2.peek()) {
                stack1.pop();
                stack2.pop();
            }else {
                return stack1.pop();
            }
        }
        return null;
    }
    //根据前序遍历和中序遍历构造一颗二叉树
    /*1.根据前序遍历找到根   2.在中序遍历中找到根的位置*/
    //public int i = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root = buildTreeChild(preorder, inorder, 0,
                inorder.length - 1);
        return root;
    }
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,
                                   int begin, int end) {
        if (begin > end) return null;//如果下标越界，此时说明没有节点了
        //TreeNode root = new TreeNode(preorder[i]);
        //找到当前根在中序遍历中的位置
        int rootIndex = findIndex(inorder,begin, end, preorder[i]);
        i++;
        root.left = buildTreeChild(preorder,inorder,begin,rootIndex-1);
        root.right = buildTreeChild(preorder, inorder, rootIndex+1,end);
        return root;
    }

    private int findIndex(int[] inorder, int begin, int end, int key) {
        for (int j = begin; j <= end; j++) {
            if (key == inorder[j]) return j;
        }
        return -1;
    }
    //根据中序遍历和后序遍历来创建一颗二叉树
    /*1.先从后续遍历中找到根，之后在中序遍历中找到根的位置*/
    /*然后i--，要注意，先创建的是右树，然后创建左树*/
    public int a;
    public TreeNode buildTree3(int[] inorder, int[] postorder) {
        a = postorder.length - 1;
        TreeNode root = buildChildTree(inorder,postorder,
                 0, inorder.length - 1);
        return root;
    }
    public TreeNode buildChildTree(int[] inorder,int[] postorder,
                                   int begin, int end) {
        //TreeNode root = new TreeNode(postorder[a]);
        int rootIndex = findIndex(inorder, begin, end, postorder[a]);
        a--;
        root.right = buildChildTree(inorder,postorder,rootIndex + 1,end);
        root.left = buildChildTree(inorder, postorder, begin, rootIndex - 1);
        return root;
    }
    //根据二叉树创建字符串
    /*要以前序遍历的方式来创建这个字符串*/
    public String tree2str(TreeNode root) {
        if (root == null) return null;
        StringBuilder builder = new StringBuilder();
        tree2strChild(root, builder);
        /*1.左边为空，右边为空  2.左边不为空右边为空  3.左边为空右边不为空*/
        return builder.toString();
    }
    public void tree2strChild(TreeNode root, StringBuilder builder) {
        if (root == null) return;
        builder.append(root.val);
        //左子树为空或者不为空
        if (root.left != null) {
            builder.append("(");
            tree2strChild(root.left,builder);
            builder.append(")");
        }else {
            //左边为空的情况下考虑右边
            if (root.right != null) {
                builder.append("()");
            }else {
                return;
            }
        }
        //右子树为空或者不为空
        if (root.right != null) {
            builder.append("(");
            tree2strChild(root.right,builder);
            builder.append(")");
        }else {
            return;
        }
    }
    //判断一棵树是否为完全二叉树
    //用合适的数据结构: 队列
    /*每次从队列中取出一个节点，不为空：把左子树和右子树带进来，
    * 为空：开始判断队列中剩余的元素*/
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                //如果cur为空说明左和右都是空的了，此时就去判断队列中的元素是否都是空的
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if (tmp != null) return false;
        }
        return true;
    }
    //非递归实现前序遍历
    public List<Integer> preorderTraversalNor(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }
    //非递归实现中序遍历
    public List<Integer> inorderTraversalNor(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);
            cur = top.right;
        }
        return list;
    }
    //非递归实现后序遍历
    public List<Integer> postorderTraversalNor(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            //此时需要注意：当打印之后top.right之后就不要再次打印了
            //所以prev记录的是 是否打印过top.right这个节点
            if (top.right == null || prev == top.right) {
                stack.pop();
                list.add(top.val);
                prev = top;
            }else {
                cur = top.right;
            }
        }
        return list;
    }
}

